/**
 * //设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
 * //
 * // 示例 1:
 * //
 * // 输入: nums = [5,6,5], target = 11
 * //输出: [[5,6]]
 * //
 * // 示例 2:
 * //
 * // 输入: nums = [5,6,5,6], target = 11
 * //输出: [[5,6],[5,6]]
 * //
 * // 提示：
 * //
 * //
 * // nums.length <= 100000
 * //
 * //
 * // Related Topics 数组 哈希表 双指针 计数 排序 👍 40 👎 0
 */

package com.xixi.basicAlgroithms.dualPointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ID_interview_16_24_PairsWithSumLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_16_24_PairsWithSumLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> pairSums(int[] nums, int target) {
            //保存结果
            List<List<Integer>> res = new ArrayList<>();


            //先排序
            Arrays.sort(nums);
            int i = 0;
            int j = nums.length - 1;

            while (i < j) {
                int sum = nums[i] + nums[j];
                if (sum == target) { //等于就保留结果

                    List<Integer> pair = new ArrayList<>();
                    pair.add(nums[i]);
                    pair.add(nums[j]);
                    i++;
                    j--;
                    res.add(pair);
                } else if (sum < target) { //比target小了，需要个大数来贴,左指针右移
                    i++;
                } else { //比 target 大， 需要将一个因子减小，右指针左移
                    j--;
                }


            }


            return res;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}